/*
* File: 		stack.c
* Author: 		Akira
* Date: 		2023-11-15
* Description:  堆栈的链式存储实现
* Version: 		1.0.0
* Modify: 		None.
*/

#include "stack.h"

// 初始化
bool InitStack(LinkStack *s)
{
#if STACK_WITH_HEAD_NODE
	s->top = (LinkNode*)malloc(sizeof(LinkNode));
	if (s->top == NULL) return false;        	//内存不足，分配失败
	s->top->next = NULL;	                    //头结点之后暂时没有节点
#else
	s->top = NULL;	                         	//空表，防止脏数据
#endif

	s->length = 0;
	return true;
}

// 判断堆栈是否为空
bool StackEmpty(LinkStack *s)
{
#if STACK_WITH_HEAD_NODE
    return (s->top->next == NULL);
#else
	return (s->top == NULL);
#endif
}

// 入栈(头插法)
bool PushStack(LinkStack *s, ElemType x)
{
	LinkNode* newnode = (LinkNode*)malloc(sizeof(LinkNode));
	if (newnode == NULL) return false;	    //内存分配失败

	newnode->data = x;
#if STACK_WITH_HEAD_NODE
	newnode->next = s->top->next;	        //新节点插入到头结点之后
	s->top->next = newnode;
#else
	newnode->next = s->top;	                //前插节点	
	s->top = newnode;	                    //s指向新节点
#endif

	s->length++;
	return true;
}

// 出栈(头删法)
bool PopStack(LinkStack *s, ElemType* x)
{
#if STACK_WITH_HEAD_NODE
    if(s->top->next == NULL) return false;      //栈空，报错
    *x = s->top->next->data;                    //x记录栈顶元素
	LinkNode* p = s->top->next;	               	//p指向栈顶节点
	s->top->next = p->next;		
#else
	if (s->top == NULL) return false;          	//栈空，报错
	*x = s->top->data;	                       	//x记录栈顶元素
	LinkNode* p = s->top;
	s->top = p->next;
#endif
	free(p);	                              	//释放栈顶节点

	s->length--;
	return true;
}

// 读取栈顶元素
bool GetTop(LinkStack *s, ElemType* x)
{
#if STACK_WITH_HEAD_NODE
    if (s->top->next == NULL) return false;  	//栈空，报错
	*x = s->top->next->data;	                //x记录栈顶元素
#else
	if (s->top == NULL) return false;           //栈空，报错
	*x = s->top->data;
#endif
	return true;
}

//求堆栈长度
int LengthStack(LinkStack *s)
{
#if STACK_WITH_HEAD_NODE
	return s->length;
#else
	int count = 0;
	LinkNode* p = s->top;
	while(p != NULL)
	{
		++count;
		p = p->next;
	}
	return count;
#endif
}
